# Bezout's lemma.
Or, Bezout's identity. Or actually, Bachet's theorem. Or, actually, Euclid's theorem, as it is argued that it is already known in Euclid's *Elements*. One can probably attribute this misattribution to Bourbaki.
In any case, it states the following:
> For $a, b$ positive integers, there exists integers $x,y$ such that $$
ax + by = \gcd(a,b).
$$
Proof. To show the existence of such integers $x,y$, we consider the set $$
A = \set{ax+by:x,y \in \mathbb{Z}, ax+by > 0}.
$$
Note that both $a,b \in A$, so $A$ is not empty. And since $A \subset \mathbb{N}$, by well-ordering principle, $A$ has a minimal element. Say $$
d = \min A = ax + by
$$for some $x,y \in \mathbb{Z}$. We now show $d = \gcd(a,b)$.
By division algorithm, we have $a = qd + r$ for some $q\ge 0$ and $0\le r < d$. Suppose $r > 0$, then note that $$
r = a -qd.
$$But $d = ax + by$, so $r = a - q(ax+by) =a-qax-qby=a(1-qx)+b(-qy) \in A$. But, $r < d$, which contradicts the minimality of $d$. Hence $r = 0$, and $d \mid a$.
Similarly by the same argument, we also have $d \mid b$. Hence $d$ is a common divisor of $a$ and $b$.
We now show $d$ is the greatest such divisor. Let $t$ be a common divisor of $a$ and $b$, where $t \mid a$ and $t \mid b$. Since $d = ax + by$, this shows $t \mid d$. Hence $d$ is $\gcd(a,b)$. $\blacksquare$
Let us denote $x,y$ to be the Bezout's coefficients for positive integers $a,b$ such that $ax + by = \gcd(a,b)$. The proof above gave a non-constructive proof of their existence. We now demonstrate how to compute for these coefficients.